package 力扣日常刷题.木23一月.第03天303;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 帅小伙
 * @date 2022/3/3
 * @description
 */
public class Demo25直线上最多的点数 {

    public int maxPoints(int[][] points) {
        int n = points.length;
        int ans = 1;

        for (int i = 0; i < n; i++) {
            HashMap<String, Integer> map = new HashMap<>();

            // 从i最多的点
            int max = 0;
            int x1 = points[i][0],y1=points[i][1];
            for (int j = i + 1; j < n; j++) {
                int x2 = points[j][0],y2=points[j][1];
                int a = x1 - x2,b = y1-y2;
                int k = gcd(a,b);
                String key = (a/k)+"_"+(b/k);
                map.put(key,map.getOrDefault(key,0)+1);
                max = Math.max(max,map.get(key));
            }
            ans = Math.max(ans,max+1);
        }
        return ans;
    }

    public int gcd(int a,int b){
        return b == 0 ? a : gcd(b,a%b);
    }

}
